package tree.二叉树的最大路径和;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public int maxPathSum(TreeNode root) {
        /**
         * 经过当前节点的最大路径和 = max(左子数的左子树 ，左子数的右子树 ) + max(右子数的左子树 ，右子数的右子树 ) + currentVal
         * 如果左右子树是负数，则需要舍弃
         */
        int[] maxValue = new int[]{Integer.MIN_VALUE};
        childMax(root ,maxValue);
        return maxValue[0];
    }

    public int childMax(TreeNode node ,int[] maxValue ) {
        if (node == null) {
            return 0 ;
        }
        int currentVal = node.val;
        int left = childMax(node.left,maxValue);
        int right = childMax(node.right,maxValue);
        if(left < 0 ){
            left = 0 ;
        }
        if (right < 0 ){
            right = 0;
        }
        int max = Math.max(left + currentVal, right + currentVal);
        maxValue[0] = Math.max(maxValue[0],left + currentVal  + right);
        return max;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int i = solution.maxPathSum(new TreeNode(-11, new TreeNode(-22), new TreeNode(-3 , new TreeNode(-4),new TreeNode(-5))));
        System.out.println(i);
    }

}
